Advances in telecommunications systems technology have resulted in a variety of telecommunications systems and services being available for use. These systems include cellular telephone networks, personal communications systems, various paging systems, and various wireline and wireless data networks. Cellular telephone networks currently in use in the United States include the AMPS analog system, the digital IS-136 time division multiplexed (TDMA) system, and the digital IS-95 digital code division multiplexed (CDMA) system. In Europe the Global Services for Mobile (GSM) digital system is most widely used. These cellular systems operate in the 800-900 Mhz range. Personal communications systems (PCS) are also currently being deployed in the United States. Many PCS systems are being developed for the 1800-1900 MHz range, with each based on one of the major cellular standards.
In each of the above mentioned telecommunications systems, it may often be desirable for the operators of the system to provide secure communications to users of the system. This may include sending a secure message between two mobile stations operating in the system. In many cases the message may be a text message of finite length, such as a text message.
In analog systems, such as AMPS, it is very difficult to provide security for communications. The analog nature of the signals carrying the communication between two users does not permit easy or efficient encryption. In fact, in standard AMPS, no encryption is used and communications sent between a mobile station and base station may be monitored and intercepted. Anyone having a receiver capable of tuning to the frequencies used for the communication channels may intercept a message at anytime, without being detected. The possibility of interception has been one negative factor connected with analog systems such as AMPS. Because of this potential for interception, AMPS type systems have not been favored for certain business or governmental uses, where sending a secure message is a requirement.
The newer digital systems such as GSM, IS-136, and IS-95 have been developed so as to include encryption services for communications privacy. The digital nature of the speech or data signals carrying the communications between two users in these digital systems allows the signals to be processed through an encryption device to produce a communications signal that appears to be random or pseudorandom in nature, until it is decrypted at an authorized receiver. When it is desired to send a secure message in such a system, the encryption feature of the system can be used to encrypt the message. As an example, the short message service (SMS) feature specified in these standards could be used to send a text message that is encrypted according to the system encryption algorithm.
In the GSM, IS-136, and IS-95 systems, the encryption is performed on message transmissions between each user and the system by using a secret key value, "private key", where the key is known only to the system and the user communicating with the system. The system standards under consideration for PCS networks may also include encryption services that are based on the encryption techniques specified in the digital standard from which a particular PCS standard is derived, i.e., GSM, IS-136, or IS-95.
In GSM the system operator controls the security process by issuing a subscriber identity module(SIM) to each system user. The SIM is a plug-in chip or card that must be inserted into a mobile station that a user intends to make or receive calls through. The SIM contains a 128 bit number called the Ki that is unique for each user. The Ki is used for both authentication and deriving an encryption key. In GSM a challenge and response procedure is used to authenticate each user and generate encryption bits from Ki for the user. The challenge and response procedure may be executed at the discretion of the home system.
When a GSM mobile is operating in its home system, after the user has identified himself by sending in his international mobile system identity/temporary mobile system identities(IMSI/TMSI), a 128-bit random number(RAND) is generated in the system and combined with the mobile user's Ki to generate a 32-bit response (SRES). The system then transmits RAND to the mobile which, in turn, computes its own SRES value from the mobile user's Ki, and transmits this RAND back to the system. If the two SRES values match, the mobile is determined to be authentic. Encryption bits for communications between the mobile and systems are generated in both the mobile and network by algorithms using RAND and Ki to produce an encryption key "Kc". Kc is then used at both ends to provide secure communications. When a GSM mobile is roaming, the RAND, SRES and Kc values are transferred to a visited system upon registration of the user in the visited system or, upon a special request from a visited system. The Ki value is never available other then in the home system and the user's SIM.
The IS-136 and IS-95 authentication and encryption procedures are identical to each other and, similar to the GSM authentication and encryption procedures. In IS-136 and IS-95 systems a challenge response method is also utilized. The IS-136 and IS-95 method utilizes a security key called the "A-key". The 64-bit A-key for each mobile is determined by the system operators. The A-key for each mobile is stored in the home system of the mobile's owner and in the mobile itself. The A-key may be initially communicated to the mobile owner in a secure manner, such as the United States mail. The owner can then enter the A-key into the mobile via the keypad. Alternately, the A-key may be programmed into the mobile station at the factory or place of service. The A-key is used to generate shared secret data(SSD) in both of the mobile and the home system from a predetermined algorithm. SSD for each mobile may be periodically derived and updated from the A-key of that particular mobile by use of an over the air protocol that can only be initiated by the home system operator.
In IS-136 and IS-95 authentication and encryption, a 32-bit global challenge is generated and broadcast at predetermined intervals within systems in the service area of the mobile. When a mobile attempts system registration/call setup access in the home system, the current global challenge response is used to compute, in the mobile, an 18-bit authentication response from the mobile's SSD. An access request message, including the authentication response and a call count value for the mobile, is then sent to the home system from the mobile. Upon receiving the access request the home system will compute its own response value using the global challenge and the mobile's SSD. If the mobile is verified as authentic, by comparison of the authentication responses, the mobile's SSD and other relevant data, including the call count value, the mobile is registered.
When a mobile attempts system registration/call setup access in a visited system, the current global challenge response is used to compute, in the mobile, the 18-bit authentication response from the mobile's SSD. An access request message is then sent to the visited system from the mobile. For initial registration accesses in a visited system, the access request message includes the authentication response computed in the mobile. The authentication response and global challenge are then sent to the home system of the mobile, where the home system will compute its own response value using the global challenge and the mobile's SSD. If the mobile is verified as authentic, by comparing the authentication responses, the mobile's SSD and other relevant data, including the call count value, is then sent to the visited system and the mobile is registered. When a call involving the mobile is setup, a current authentication response value and call count are sent to the system from the mobile along with the call setup information. Upon receiving the call setup information, the visited system retrieves the stored SSD and call count values for the requesting mobile. The visited system then computes an authentication response value to verify that the the received SSD value and the current global challenge produce the the same response as that produced in the mobile. If the authentication responses and call counts match, the mobile is allowed call access. If communications security is desired, an encryption key is produced in both the mobile and system by using the global challenge and the mobile's SSD as input to generate encryption key bits.
Further background for such techniques as those used in GSM and, the IS-136 and IS-95 systems may be found in the article "Techniques for Privacy and Authentication in Personal Communications Systems" by Dan Brown in IEEE Personal Communications, dated August 1995, at pages 6-10.
While the above described private key procedures used in the GSM, IS-136 and IS-95 systems provide communications security, none of these procedures is entirely immune to interception and eavesdropping. All of the procedures require that a user's A-key or Ki value be known both in the mobile station and home system. They also require that the user's SSD or Kc value be known at both ends of the communications link, i.e., in the system and in the mobile. Each of these values could potentially be corrupted and become known to a potential interceptor . An individual knowing the Ki or A-key of a user, or an individual who intercepts the Kc or SSD of the user in intersystem communications, could potentially intercept and eavesdrop on communications that were intended to be secure and private. Additionally, since each user's keys are available at a base station with which they are communicating, encrypted communications involving two mobile stations connected through a base station of a system could be breached at the base station.
Public key encryption methods are methods in which a user is assigned a encryption key that is public, i.e., may be known and revealed publicly, but is also assigned a private decryption key that is known only to the user. Only an intended receiving user's decryption key can decrypt a encrypted message meant for the intended receiving user, i.e., decrypt a message encrypted using the intended receiving user's encryption key. In a public key encryption telecommunication system, the user would be allowed to keep the decryption key to himself, away from base stations or the system. Since the key necessary for decrypting a message is known only to the receiving user, public key encryption methods could provide more secure communications than are obtainable with the current encryption techniques being, used in, for example, GSM, IS-136, or IS-95.
In a cellular system using conventional public key encryption, if a mobile station X were to send a encrypted message to mobile station Y, mobile station X is required to know both the public encryption key for mobile station Y and, the algorithm that must be used with the encryption key of mobile station Y. It would also be required that Mobile X be capable of performing the encryption of the message using mobile station Y's encryption key and algorithm. These requirements of conventional public key encryption may present some difficulties or not be quite optimal for use in cellular systems in certain situations.
One difficulty in using public key encryption techniques is that the calculations involved in encryption and decryption may require much more in the way of computational resources then is required by private key systems. In a mobile station such computational resources may be limited. The requirements on resources may be even greater if two mobile station users desire to exchange a message securely, with each user using a different encryption/decryption algorithm. This could be the case, for example, when a roaming mobile station enters a system in which the system operator has implemented his own unique algorithm that is different from the roaming mobile station's home system's algorithm. In this case, each particular mobile station would be required to be capable of performing encryption with the other user's algorithm and, decryption with that particular mobile station user's algorithm. Such a requirement could be difficult to meet, for example, if the algorithm used for encryption required more computational resources then were available in the mobile station performing the encryption. Also, the code and data for performing particular algorithms would have to be stored in each mobile station or transmitted to the mobile station prior to commencement of encryption, creating further demands on mobile station computational resources.
Another potential difficulty in using public key encryption techniques in a cellular system involves the requirement that the sending mobile station should know the encryption key of the receiving mobile station in order to assure that the message is only available to the sending or receiving mobile stations. In certain public key encryption techniques the encryption keys may each be very large, possibly a sequence of numbers, and it may be difficult to store encryption keys for all potential receiving mobile stations in a single mobile station. It may also be difficult to transmit the key of a receiving mobile station to a sending mobile station on an as needed basis, for example during call setup, if the key is very large.